class Solution {
    int m, n, dx[4] = { 0, 0, 1, -1 }, dy[4] = { 1, -1, 0, 0 };
    void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>> &visited)
    {
        visited[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && h[x][y] >= h[i][j] && visited[x][y] == false)
                dfs(h, x, y, visited);
        }
    }
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
        m = h.size(), n = h[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n));
        vector<vector<bool>> alt(m, vector<bool>(n));

        // 从边界(海岸线)反向推出水能从哪些地方流入大洋
        // 先处理太平洋
        for(int j = 0; j < n; j++)
                dfs(h, 0, j, pac);
        for(int i = 0; i < m; i++)
                dfs(h, i, 0, pac);

        // 再处理大西洋
        for(int j = 0; j < n; j++)
                dfs(h, m - 1, j, alt);
        for(int i = 0; i < m; i++)
                dfs(h, i, n - 1, alt);

        vector<vector<int>> ret;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(pac[i][j] && alt[i][j])
                    ret.push_back({i, j});
        return ret;
    }
};



// 下面是我自己实现的代码
// class Solution {
//     vector<vector<int>> count;
//     vector<vector<bool>> visited;
//     int m, n, dx[4] = { 0, 0, 1, -1 }, dy[4] = { 1, -1, 0, 0 };
//     void dfs(vector<vector<int>>& h, int i, int j)
//     {
//         visited[i][j] = true;
//         count[i][j]++;
//         for(int k = 0; k < 4; k++)
//         {
//             int x = i + dx[k], y = j + dy[k];
//             if(x >= 0 && x < m && y >= 0 && y < n && h[x][y] >= h[i][j] && visited[x][y] == false)
//                 dfs(h, x, y);
//         }
//     }
// public:
//     vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
//         m = h.size(), n = h[0].size();
//         count = vector<vector<int>>(m, vector<int>(n));
//         visited = vector<vector<bool>>(m, vector<bool>(n));

//         // 从边界(海岸线)反向推出水能从哪些地方流入大洋
//         // 先处理太平洋
//         for(int j = 0; j < n; j++)
//             if(visited[0][j] == false)
//                 dfs(h, 0, j);
//         for(int i = 0; i < m; i++)
//             if(visited[i][0] == false)
//                 dfs(h, i, 0);

//         // 重置visited数组，以便遍历大西洋
//         for(int i = 0; i < m; i++)
//         {
//             visited.clear();
//             visited[i].resize(n);
//         }

//         // 再处理大西洋
//         for(int j = 0; j < n; j++)
//             if(visited[m - 1][j] == false)
//                 dfs(h, m - 1, j);
//         for(int i = 0; i < m; i++)
//             if(visited[i][n - 1] == false)
//                 dfs(h, i, n - 1);


//         vector<vector<int>> ret;
//         for(int i = 0; i < m; i++)
//             for(int j = 0; j < n; j++)
//                 if(count[i][j] == 2)
//                     ret.push_back({i, j});
//         return ret;
//     }
// };